package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0328_01 {

    class MaxQueue {

        /**
         * 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
         *
         * 若队列为空，pop_front 和 max_value 需要返回 -1
         *
         * 示例 1：
         *
         * 输入:
         * ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
         * [[],[1],[2],[],[],[]]
         * 输出: [null,null,null,2,1,2]
         * 示例 2：
         *
         * 输入:
         * ["MaxQueue","pop_front","max_value"]
         * [[],[],[]]
         * 输出: [null,-1,-1]
         *
         * 1 <= push_back,pop_front,max_value的总操作数 <= 10000
         * 1 <= value <= 10^5
         *
         *
         * 思路分析：
         * 对于普通队列 入队 和 出队的时间复杂度均为 O（1） ，本题最大的难点为实现查找最大值 max 时的时间复杂度仍然为 O（1）
         * 若队列中存储N个元素，从中获取最大值需要遍历队列，时间复杂度为 O（N） ，单从算法角度上无优化空间
         *
         * 最直观的方法时  维护一个最大值变量，在元素入队时，更新此变量即可；但是当最大值出队后，无法确定下一个次最大值，不可行
         *
         * 考虑 利用 数据结构来实现，即经常使用的 空间换时间，如下图所示，
         * 考虑构建一个递减列表来保存 队列 所有递减的元素，递减链表随着入队和出队操作实时更新，这样队列最大元素就始终对应
         * 递减列表的首元素，实现了获取最大值O（1） 的时间复杂度
         * 为了实现递减列表，需要使用 双向队列
         * 1、当指向入队时，若入队一个比队列某些元素更大的数字x，则为了保持此列表递减，需要将双向队列 尾部所有小于x的元素弹出
         * 2、当执行出队时，若出队的元素是最大元素，则 双向队列 需要同时将首元素出队，以保持队列和上香队列的元素的一致性
         * 注意：使用双向队列的原因，维护递减列表需要元素队首弹出、队尾插入、队尾部弹出操作结尾 O（1）的时间复杂度
         */
        Queue<Integer> queue;
        Deque<Integer> deque;
        public MaxQueue() {
            queue = new LinkedList<>();
            deque = new LinkedList<>();
        }

        /**
         * 当双向队列 deque为空，则返回 -1；
         * 否则，返回 deque 首元素
         * @return
         */
        public int max_value() {
            return deque.isEmpty() ? -1 :deque.peekFirst();
        }

        /**
         * 将元素 value 入队 queue
         * 将双向队列中队尾所有小于 value 的元素弹出 （保持 deque 非单调递减），并将 value入队 deque
         * @param value
         */
        public void push_back(int value) {
            queue.offer(value);
            // 将双向队列中队尾所有小于 value 的元素弹出
            while (!deque.isEmpty() && deque.peekLast() < value) {
                deque.pollLast();
            }
            // 队尾部添加
            deque.offerLast(value);
        }

        /**
         * 若队列 queue为空，则直接返回 -1
         * 否则，将queue首元素出队
         * 若 deque 首元素 和 queue 首元素相等，则将 deque首元素出队（保持两队列 元素一致）；
         *
         * @return
         */
        public int pop_front() {
            if (queue.isEmpty()){
                return -1;
            }
            // 涉及双向列表为 单调不增的原因：若列表 queue中存在两个值相同的最大元素，此时 queue 和 deque 同时弹出一个最大元素
            // 而 queue中还有一个此最大元素，即采用单调递减将导致两队列中的元素不一致
            // 单调不增 不等于 单调递减
            if (queue.peek().equals(deque.peekFirst())){
                deque.pollFirst();
            }
            return queue.poll();
        }
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3() {

    }

}
